{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Beauty in the Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumOfBeauties"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组美丽值求和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 。对于每个下标 <code>i</code>（<code>1 &lt;= i &lt;= nums.length - 2</code>），<code>nums[i]</code> 的 <strong>美丽值</strong> 等于：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2</code>，对于所有 <code>0 &lt;= j &lt; i</code> 且 <code>i &lt; k &lt;= nums.length - 1</code> ，满足 <code>nums[j] &lt; nums[i] &lt; nums[k]</code></li>\n",
    "\t<li><code>1</code>，如果满足 <code>nums[i - 1] &lt; nums[i] &lt; nums[i + 1]</code> ，且不满足前面的条件</li>\n",
    "\t<li><code>0</code>，如果上述条件全部不满足</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回符合 <code>1 &lt;= i &lt;= nums.length - 2</code> 的所有<em> </em><code>nums[i]</code><em> </em>的 <strong>美丽值的总和</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>对于每个符合范围 1 &lt;= i &lt;= 1 的下标 i :\n",
    "- nums[1] 的美丽值等于 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,4,6,4]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>对于每个符合范围 1 &lt;= i &lt;= 2 的下标 i :\n",
    "- nums[1] 的美丽值等于 1\n",
    "- nums[2] 的美丽值等于 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [3,2,1]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>对于每个符合范围 1 &lt;= i &lt;= 1 的下标 i :\n",
    "- nums[1] 的美丽值等于 0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-beauty-in-the-array](https://leetcode.cn/problems/sum-of-beauty-in-the-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-beauty-in-the-array](https://leetcode.cn/problems/sum-of-beauty-in-the-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[2,4,6,4]', '[3,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums); r_mns = nums[:]; mn = nums[-1]\n",
    "        for i in range(n-1,1,-1):\n",
    "            if mn > r_mns[i]:\n",
    "                mn = r_mns[i]\n",
    "            else:\n",
    "                r_mns[i] = mn\n",
    "        ans = 0; mx = nums[0]\n",
    "        for i in range(1,n-1):\n",
    "            if mx < nums[i] < r_mns[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "            if mx < nums[i]:\n",
    "                mx = nums[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        r_mns = [inf] * (n+1)\n",
    "        for i in range(n-1,1,-1):\n",
    "            r_mns[i] = min(nums[i], r_mns[i+1])\n",
    "        \n",
    "        ans = 0\n",
    "        mx = nums[0]\n",
    "        for i in range(1,n-1):\n",
    "            if mx < nums[i] < r_mns[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "            if mx < nums[i]:\n",
    "                mx = nums[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        suffix = [0] * len(nums)\n",
    "\n",
    "        suffix[-1] = nums[-1]\n",
    "\n",
    "        for i in range(len(suffix) - 2, -1, -1):\n",
    "            suffix[i] = min(suffix[i + 1], nums[i])\n",
    "\n",
    "        \n",
    "        max_ = nums[0]\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums) - 1):\n",
    "            if max_ < nums[i] < suffix[i + 1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "            max_ = max(max_, nums[i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mnsuf = [0] * n\n",
    "        mnsuf[n-1] = nums[n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            mnsuf[i] = min(mnsuf[i+1], nums[i])\n",
    "        ans = 0\n",
    "        mx = nums[0]\n",
    "        for i in range(1, n - 1):\n",
    "            if mx < nums[i] < mnsuf[i+ 1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            mx = max(mx, nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        r_mns = nums[:]\n",
    "        for i in range(n-2,1,-1):\n",
    "            if r_mns[i] > r_mns[i+1]:\n",
    "                r_mns[i] = r_mns[i+1]\n",
    "        \n",
    "        ans = 0\n",
    "        mx = nums[0]\n",
    "        for i in range(1,n-1):\n",
    "            if mx < nums[i] < r_mns[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "            if mx < nums[i]:\n",
    "                mx = nums[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        minv = [0] * n\n",
    "        minv[n - 1] = nums[n - 1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            minv[i] = min(minv[i + 1], nums[i])\n",
    "        ret = 0\n",
    "        maxv = nums[0]\n",
    "        for i in range(1, n - 1):\n",
    "            if maxv < nums[i] < minv[i + 1]:\n",
    "                ret += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ret += 1\n",
    "            maxv = max(maxv, nums[i])\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        r_mns = nums[:]\n",
    "        for i in range(n-2,1,-1):\n",
    "            if r_mns[i] > r_mns[i+1]:\n",
    "                r_mns[i] = r_mns[i+1]\n",
    "        \n",
    "        ans = 0\n",
    "        mx = nums[0]\n",
    "        for i in range(1,n-1):\n",
    "            if mx < nums[i] < r_mns[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "            if mx < nums[i]:\n",
    "                mx = nums[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        suf_min = [0] * n \n",
    "        suf_min[-1] = nums[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            suf_min[i] = min(nums[i], suf_min[i+1])\n",
    "        \n",
    "        ans ,pre_max = 0, nums[0]\n",
    "        for i in range(1, n-1):\n",
    "            if pre_max < nums[i] < suf_min[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            pre_max = max(pre_max, nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left_max = [0] * n\n",
    "        right_min = [0] * n\n",
    "        \n",
    "        left_max[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            left_max[i] = max(left_max[i-1], nums[i])\n",
    "        \n",
    "        right_min[n-1] = nums[n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            right_min[i] = min(right_min[i+1], nums[i])\n",
    "        \n",
    "        beauty_sum = 0\n",
    "        for i in range(1, n-1):\n",
    "            if left_max[i-1] < nums[i] < right_min[i+1]:\n",
    "                beauty_sum += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                beauty_sum += 1\n",
    "        \n",
    "        return beauty_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        l_max = -float(\"inf\")\n",
    "\n",
    "        ll = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            if nums[i] > l_max :\n",
    "\n",
    "                l_max = nums[i]\n",
    "\n",
    "            ll[i] = l_max\n",
    "\n",
    "        \n",
    "\n",
    "        r_min = float(\"inf\")\n",
    "\n",
    "        rr = [0] * n\n",
    "\n",
    "        for j in range(n-1, -1, -1):\n",
    "\n",
    "            if nums[j] < r_min :\n",
    "\n",
    "                r_min = nums[j]\n",
    "\n",
    "            rr[j] = r_min\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "\n",
    "            if nums[i] > ll[i - 1] and nums[i] < rr[i + 1]:\n",
    "\n",
    "                res += 2\n",
    "\n",
    "            elif nums[i] > nums[i - 1] and nums[i] < nums[i + 1]:\n",
    "\n",
    "                res += 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = [0]*n\n",
    "        maxnum = float('-inf')\n",
    "        for i in range(n):\n",
    "            maxnum = max(maxnum, nums[i])\n",
    "            left[i] = maxnum\n",
    "        right = [0]*n \n",
    "        minnum = float('inf')\n",
    "        for i in range(n-1,-1,-1):\n",
    "            minnum = min(minnum, nums[i])\n",
    "            right[i] = minnum\n",
    "        result = 0\n",
    "        for i in range(1,n-1):\n",
    "            if(left[i-1] < nums[i] < right[i+1]):\n",
    "                result += 2\n",
    "            elif(nums[i-1] < nums[i] < nums[i+1]):\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        left = nums[0]\n",
    "        right = nums[-1]\n",
    "        dp = list()\n",
    "        ans = 0\n",
    "        for i in range(1, length - 1):\n",
    "            if nums[i] > left:\n",
    "                dp.append(2)\n",
    "            elif nums[i] > nums[i - 1]:\n",
    "                dp.append(1)\n",
    "            else:\n",
    "                dp.append(0)\n",
    "            left = max(left, nums[i])\n",
    "        for i in range(length - 2, 0, -1):\n",
    "            if nums[i] < right:\n",
    "                if dp[i - 1] == 2:\n",
    "                    ans += 2\n",
    "                elif dp[i - 1] == 1:\n",
    "                    ans += 1\n",
    "            elif nums[i] < nums[i + 1]:\n",
    "                if dp[i - 1] > 0:\n",
    "                    ans += 1\n",
    "            right = min(right, nums[i])\n",
    "        print(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [0] * n, [0] * n\n",
    "        l[0] = nums[0]\n",
    "        for i in range(1, n): l[i] = max(l[i - 1], nums[i])\n",
    "        r[-1] = nums[-1]\n",
    "        for i in range(n - 2, -1, -1): r[i] = min(r[i + 1], nums[i])\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n - 1):\n",
    "            if l[i - 1] < nums[i] < r[i + 1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        left = nums[0]\n",
    "        right = nums[-1]\n",
    "        dp = list()\n",
    "        ans = 0\n",
    "        for i in range(1, length - 1):\n",
    "            if nums[i] > left:\n",
    "                dp.append(2)\n",
    "            elif nums[i] > nums[i - 1]:\n",
    "                dp.append(1)\n",
    "            else:\n",
    "                dp.append(0)\n",
    "            left = max(left, nums[i])\n",
    "        for i in range(length - 2, 0, -1):\n",
    "            if nums[i] < right:\n",
    "                if dp[i - 1] == 2:\n",
    "                    ans += 2\n",
    "                elif dp[i - 1] == 1:\n",
    "                    ans += 1\n",
    "            elif nums[i] < nums[i + 1]:\n",
    "                if dp[i - 1] > 0:\n",
    "                    ans += 1\n",
    "            right = min(right, nums[i])\n",
    "        print(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        post = [inf]*(n+1)\n",
    "        for i in range(n-1, -1,-1):\n",
    "            a, b = post[i+1], nums[i]\n",
    "            post[i] = a if a < b else b\n",
    "\n",
    "        pre = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            a, b = pre[i], nums[i]\n",
    "            pre[i+1] = a if a > b else b\n",
    "        ans = 0\n",
    "        for i in range(1, n-1):\n",
    "            if pre[i]< nums[i] < post[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1]<nums[i]<nums[i+1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        n = len(nums)\n",
    "        fma = [0]*n\n",
    "        fmi = [0]*n\n",
    "        black = set()\n",
    "        for i in range(n-1):\n",
    "            if i==0:\n",
    "                fma[i] = nums[i]\n",
    "                fmi[n-i-1] = nums[n-i-1]\n",
    "            else:\n",
    "                if nums[i-1]<nums[i]<nums[i+1]:\n",
    "                    s += 1\n",
    "                fma[i] = max(fma[i-1],nums[i])\n",
    "                if fma[i-1] == nums[i]:\n",
    "                    black.add(fma[i])\n",
    "                fmi[n-i-1] = min(fmi[n-i],nums[n-i-1])\n",
    "                if fmi[n-i]==nums[n-i-1]:\n",
    "                    black.add(fmi[n-i])\n",
    "        fma[0] = -1\n",
    "        fmi[-1] = 9.1\n",
    "        for i,j in zip(fma,fmi):\n",
    "            if i==j and j not in black:\n",
    "                s+=1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        leftMax,rightMin = [0] * n, [0] * n\n",
    "        leftMax[0] = nums[0]\n",
    "        rightMin[-1] = nums[-1]\n",
    "        # 计算左边的最大值\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > leftMax[i-1]:\n",
    "                leftMax[i] = nums[i]\n",
    "            else:\n",
    "                leftMax[i] = leftMax[i-1]\n",
    "        # 计算右边最小值\n",
    "        for j in range(n-2, -1, -1):\n",
    "            if nums[j] < rightMin[j + 1]:\n",
    "                rightMin[j] = nums[j]\n",
    "            else:\n",
    "                rightMin[j] = rightMin[j+1]\n",
    "        # 判断美丽值\n",
    "        for i in range(1,n-1):\n",
    "            if leftMax[i-1] < nums[i] < rightMin[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                pass\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        leftmx = [nums[0]]; rightmn = nums[-1]; n = len(nums); ans = 0\n",
    "        for i in range(1, n - 1):\n",
    "            if nums[i - 1] < nums[i] < nums[i + 1]:  ans += 1\n",
    "            leftmx += max(nums[i], leftmx[-1]),\n",
    "        for j in range(n-2, 0, -1):\n",
    "            if leftmx[j-1] < nums[j] < rightmn: ans += 1\n",
    "            rightmn = min(rightmn, nums[j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        leftMax,rightMin = [0] * n, [0] * n\n",
    "        leftMax[0] = nums[0]\n",
    "        rightMin[-1] = nums[-1]\n",
    "        # 计算左边的最大值\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > leftMax[i-1]:\n",
    "                leftMax[i] = nums[i]\n",
    "            else:\n",
    "                leftMax[i] = leftMax[i-1]\n",
    "        # 计算右边最小值\n",
    "        for j in range(n-2, -1, -1):\n",
    "            if nums[j] < rightMin[j + 1]:\n",
    "                rightMin[j] = nums[j]\n",
    "            else:\n",
    "                rightMin[j] = rightMin[j+1]\n",
    "        # 判断美丽值\n",
    "        for i in range(1,n-1):\n",
    "            if leftMax[i-1] < nums[i] < rightMin[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                pass\n",
    "        return ans\n",
    "\n",
    "# class Solution:\n",
    "#     def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         max_v = [inf]\n",
    "#         for v in nums[::-1]:\n",
    "#             max_v = [min(max_v[0],v)] + max_v\n",
    "#         max_v = max_v[2:-1]\n",
    "\n",
    "#         min_v = [-inf]\n",
    "#         ans = 0\n",
    "#         for j,v in enumerate(nums):\n",
    "#             min_v.append(max(min_v[-1],v))\n",
    "#             if j >= 1 and j < n-1:\n",
    "#                 if v > min_v[j] and v < max_v[j-1]:\n",
    "#                     ans += 2\n",
    "#                 elif v > nums[j-1] and v < nums[j+1]:\n",
    "#                     ans += 1\n",
    "            \n",
    "#         return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums); r_mns = nums[:]; mn = nums[-1]\n",
    "        for i in range(n-1,1,-1):\n",
    "            if mn > r_mns[i]:\n",
    "                mn = r_mns[i]\n",
    "            else:\n",
    "                r_mns[i] = mn\n",
    "        ans = 0; mx = nums[0]\n",
    "        for i in range(1,n-1):\n",
    "            if mx < nums[i] < r_mns[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "            if mx < nums[i]:\n",
    "                mx = nums[i]\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = nums[:]\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i - 1] if pre[i - 1] > nums[i] else nums[i]\n",
    "        post = nums[:]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            post[i] = post[i + 1] if post[i + 1] < nums[i] else nums[i]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n - 1):\n",
    "            if pre[i - 1] < nums[i] < post[i + 1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        # 寻找情况1，如果结果等于n-2，乘以2\n",
    "        n = len(nums)\n",
    "        beauty = 0\n",
    "        big = [False] * n\n",
    "        mx = nums[0]\n",
    "        for i in range(1, n-1):\n",
    "            if nums[i-1] < nums[i] < nums[i+1]:\n",
    "                beauty += 1\n",
    "            if nums[i] > mx:\n",
    "                big[i] = True\n",
    "                mx = nums[i]\n",
    "        \n",
    "        mn = nums[-1]\n",
    "        for i in range(n-2, 0, -1):\n",
    "            if nums[i] < mn:\n",
    "                mn = nums[i]\n",
    "                if big[i]:\n",
    "                    beauty += 1\n",
    "                \n",
    "        return beauty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        r_mns = nums[:]\n",
    "        mn = nums[-1]\n",
    "        for i in range(n-1,1,-1):\n",
    "            if mn > r_mns[i]:\n",
    "                mn = r_mns[i]\n",
    "            else:\n",
    "                r_mns[i] = mn\n",
    "        \n",
    "        ans = 0\n",
    "        mx = nums[0]\n",
    "        for i in range(1,n-1):\n",
    "            if mx < nums[i] < r_mns[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "            if mx < nums[i]:\n",
    "                mx = nums[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        beauty = 0\n",
    "        big = [False] * n\n",
    "        mx = nums[0]\n",
    "        for i in range(1, n-1):\n",
    "            if nums[i-1] < nums[i] < nums[i+1]:\n",
    "                beauty += 1\n",
    "            if nums[i] > mx:\n",
    "                big[i] = True\n",
    "                mx = nums[i]\n",
    "        \n",
    "        mn = nums[-1]\n",
    "        for i in range(n-2, 0, -1):\n",
    "            if nums[i] < mn:\n",
    "                mn = nums[i]\n",
    "                if big[i]:\n",
    "                    beauty += 1\n",
    "                \n",
    "        return beauty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        # 寻找情况1，如果结果等于n-2，乘以2\n",
    "        n = len(nums)\n",
    "        beauty = 0\n",
    "        big = [False] * n\n",
    "        mx = nums[0]\n",
    "        for i in range(1, n-1):\n",
    "            if nums[i-1] < nums[i] < nums[i+1]:\n",
    "                beauty += 1\n",
    "            if nums[i] > mx:\n",
    "                big[i] = True\n",
    "                mx = nums[i]\n",
    "        \n",
    "        mn = nums[-1]\n",
    "        for i in range(n-2, 0, -1):\n",
    "            if nums[i] < mn:\n",
    "                mn = nums[i]\n",
    "                if big[i]:\n",
    "                    beauty += 1\n",
    "                \n",
    "        return beauty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        leftMax,rightMin = [0] * n, [0] * n\n",
    "        leftMax[0] = nums[0]\n",
    "        rightMin[-1] = nums[-1]\n",
    "        # 计算左边的最大值\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > leftMax[i-1]:\n",
    "                leftMax[i] = nums[i]\n",
    "            else:\n",
    "                leftMax[i] = leftMax[i-1]\n",
    "        # 计算右边最小值\n",
    "        for j in range(n-2, -1, -1):\n",
    "            if nums[j] < rightMin[j + 1]:\n",
    "                rightMin[j] = nums[j]\n",
    "            else:\n",
    "                rightMin[j] = rightMin[j+1]\n",
    "        # 判断美丽值\n",
    "        for i in range(1,n-1):\n",
    "            if leftMax[i-1] < nums[i] < rightMin[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                pass\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        r_mns = [inf] * (n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            r_mns[i] = min(nums[i], r_mns[i+1])\n",
    "        \n",
    "        ans = 0\n",
    "        mx = nums[0]\n",
    "        for i in range(1,n-1):\n",
    "            if mx < nums[i] < r_mns[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "            mx = max(mx, nums[i])\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        #预处理出nums每个位置前i个的最值\n",
    "        min_nums,max_nums=[nums[-1]]*n,[nums[0]]*n\n",
    "        for i in range(1,n):\n",
    "            max_nums[i]=max(max_nums[i-1],nums[i])\n",
    "        for i in range(n-2,-1,-1):\n",
    "            min_nums[i]=min(min_nums[i+1],nums[i])\n",
    "        #预处理完成\n",
    "        ans=0\n",
    "        for i in range(1,n-1):\n",
    "            if max_nums[i-1]<nums[i]<min_nums[i+1]:\n",
    "                ans+=2\n",
    "            elif nums[i-1]<nums[i]<nums[i+1]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        pre_mx, suf_mn = [0], [inf]\n",
    "        for x in nums:\n",
    "            pre_mx.append(max(pre_mx[-1], x))\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suf_mn.append(min(suf_mn[-1], nums[i]))\n",
    "        \n",
    "        for i in range(1, n - 1):\n",
    "            if pre_mx[i] < nums[i] and nums[i] < suf_mn[n - i - 1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] and nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        leftmx = [nums[0]]; rightmn = nums[-1]; n = len(nums); ans = 0\n",
    "        for i in range(1, n - 1):\n",
    "            if nums[i - 1] < nums[i] < nums[i + 1]:  ans += 1\n",
    "            leftmx += max(nums[i], leftmx[-1]),\n",
    "        for j in range(n-2, 0, -1):\n",
    "            if leftmx[j-1] < nums[j] < rightmn: ans += 1\n",
    "            rightmn = min(rightmn, nums[j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        leftMax,rightMin = [0] * n, [0] * n\n",
    "        leftMax[0] = nums[0]\n",
    "        rightMin[-1] = nums[-1]\n",
    "        # 计算左边的最大值\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > leftMax[i-1]:\n",
    "                leftMax[i] = nums[i]\n",
    "            else:\n",
    "                leftMax[i] = leftMax[i-1]\n",
    "        # 计算右边最小值\n",
    "        for j in range(n-2, -1, -1):\n",
    "            if nums[j] < rightMin[j + 1]:\n",
    "                rightMin[j] = nums[j]\n",
    "            else:\n",
    "                rightMin[j] = rightMin[j+1]\n",
    "        # 判断美丽值\n",
    "        for i in range(1,n-1):\n",
    "            if leftMax[i-1] < nums[i] < rightMin[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                pass\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        left_max = nums[0]\n",
    "        right_mins = [nums[-1]] * length\n",
    "\n",
    "        beautiful_sum = 0\n",
    "        for i in range(length - 2, 1, -1):\n",
    "            right_min = right_mins[i + 1]\n",
    "            if nums[i] < right_min:\n",
    "                right_min = nums[i]\n",
    "            right_mins[i] = right_min\n",
    "\n",
    "        for i in range(1, length - 1):\n",
    "            if nums[i -1] > left_max:\n",
    "                left_max = nums[i - 1]\n",
    "\n",
    "            if  left_max < nums[i] < right_mins[i + 1]:\n",
    "                beautiful_sum += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                beautiful_sum += 1\n",
    "        \n",
    "        return beautiful_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        dp_left = [float('-inf')] * n\n",
    "        dp_left[1] = nums[0]\n",
    "        for i in range(2, n):\n",
    "            dp_left[i] = max(dp_left[i - 1], nums[i - 1])\n",
    "            pass\n",
    "\n",
    "        dp_right = [sys.maxsize] * n\n",
    "        dp_right[n - 2] = nums[n - 1]\n",
    "        for i in range(n - 3, 0, -1):\n",
    "            dp_right[i] = min(dp_right[i + 1], nums[i+1])\n",
    "            pass\n",
    "\n",
    "        for i in range(1, len(nums) - 1):\n",
    "            res = self.get_v(nums, dp_left, dp_right, i)\n",
    "            result += res\n",
    "            pass\n",
    "        return result\n",
    "\n",
    "    pass\n",
    "\n",
    "\n",
    "    def get_v(self, nums, dp_left, dp_right, i):\n",
    "        if dp_left[i] < nums[i] < dp_right[i]:\n",
    "            # nums[j]-->max,nums[k]-->min\n",
    "            # max < i < min\n",
    "            return 2\n",
    "            pass\n",
    "        elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        leftMax,rightMin = [0] * n, [0] * n\n",
    "        leftMax[0] = nums[0]\n",
    "        rightMin[-1] = nums[-1]\n",
    "        # 计算左边的最大值\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > leftMax[i-1]:\n",
    "                leftMax[i] = nums[i]\n",
    "            else:\n",
    "                leftMax[i] = leftMax[i-1]\n",
    "        # 计算右边最小值\n",
    "        for j in range(n-2, -1, -1):\n",
    "            if nums[j] < rightMin[j + 1]:\n",
    "                rightMin[j] = nums[j]\n",
    "            else:\n",
    "                rightMin[j] = rightMin[j+1]\n",
    "        # 判断美丽值\n",
    "        for i in range(1,n-1):\n",
    "            if leftMax[i-1] < nums[i] < rightMin[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                pass\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        leftMax,rightMin = [0] * n, [0] * n\n",
    "        leftMax[0] = nums[0]\n",
    "        rightMin[-1] = nums[-1]\n",
    "        # 计算左边的最大值\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > leftMax[i-1]:\n",
    "                leftMax[i] = nums[i]\n",
    "            else:\n",
    "                leftMax[i] = leftMax[i-1]\n",
    "        # 计算右边最小值\n",
    "        for j in range(n-2, -1, -1):\n",
    "            if nums[j] < rightMin[j + 1]:\n",
    "                rightMin[j] = nums[j]\n",
    "            else:\n",
    "                rightMin[j] = rightMin[j+1]\n",
    "        # 判断美丽值\n",
    "        for i in range(1,n-1):\n",
    "            if leftMax[i-1] < nums[i] < rightMin[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                pass\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        leftMax,rightMin = [0] * n, [0] * n\n",
    "        leftMax[0] = nums[0]\n",
    "        rightMin[-1] = nums[-1]\n",
    "        # 计算左边的最大值\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > leftMax[i-1]:\n",
    "                leftMax[i] = nums[i]\n",
    "            else:\n",
    "                leftMax[i] = leftMax[i-1]\n",
    "        # 计算右边最小值\n",
    "        for j in range(n-2, -1, -1):\n",
    "            if nums[j] < rightMin[j + 1]:\n",
    "                rightMin[j] = nums[j]\n",
    "            else:\n",
    "                rightMin[j] = rightMin[j+1]\n",
    "        # 判断美丽值\n",
    "        for i in range(1,n-1):\n",
    "            if leftMax[i-1] < nums[i] < rightMin[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                pass\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        leftMax,rightMin = [0] * n, [0] * n\n",
    "        leftMax[0] = nums[0]\n",
    "        rightMin[-1] = nums[-1]\n",
    "        # 计算左边的最大值\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > leftMax[i-1]:\n",
    "                leftMax[i] = nums[i]\n",
    "            else:\n",
    "                leftMax[i] = leftMax[i-1]\n",
    "        # 计算右边最小值\n",
    "        for j in range(n-2, -1, -1):\n",
    "            if nums[j] < rightMin[j + 1]:\n",
    "                rightMin[j] = nums[j]\n",
    "            else:\n",
    "                rightMin[j] = rightMin[j+1]\n",
    "        # 判断美丽值\n",
    "        for i in range(1,n-1):\n",
    "            if leftMax[i-1] < nums[i] < rightMin[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                pass\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        min_l,max_l = [10**5 for i in range(len(nums))],[0 for i in range(len(nums))]\n",
    "        max_l[0] = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            max_l[i] = max(nums[i],max_l[i-1])\n",
    "        min_l[-1] = nums[-1]\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            min_l[i] = min(nums[i],min_l[i+1])\n",
    "        res = 0\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if nums[i] > max_l[i-1] and nums[i] < min_l[i+1]:\n",
    "                res += 2\n",
    "                continue\n",
    "            if nums[i] > nums[i-1] and nums[i] < nums[i+1]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        leftMax, rightMin = [0] * n, [0] * n \n",
    "        leftMax[0] ,rightMin[-1] = nums[0], nums[-1]\n",
    "\n",
    "        # search the maxmum in the left \n",
    "        for i in range(1, n):\n",
    "            if nums[i] > leftMax[i-1]:\n",
    "                leftMax[i] = nums[i]\n",
    "            else:\n",
    "                leftMax[i] = leftMax[i-1]\n",
    "\n",
    "        # search the minimum in the right\n",
    "        for j in range(n-2, -1, -1):\n",
    "            if nums[j] < rightMin[j + 1]:\n",
    "                rightMin[j] = nums[j]\n",
    "            else:\n",
    "                rightMin[j] = rightMin[j+1]\n",
    "        # 美丽值\n",
    "        for i in range(1, n-1):\n",
    "            if leftMax[i-1] < nums[i] < rightMin[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "            else:pass\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left_max, right_min = [nums[0]] * n, [nums[-1]] * n\n",
    "        for i in range(1, n):\n",
    "            left_max[i] = max(left_max[i - 1], nums[i])\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            right_min[j] = min(right_min[j + 1], nums[j])\n",
    "        ans = 0\n",
    "        for i in range(1, n - 1):\n",
    "            if nums[i] > left_max[i - 1] and nums[i] < right_min[i + 1]:\n",
    "                ans += 2\n",
    "            elif nums[i] > nums[i - 1] and nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        dp_left = [float('-inf') for _ in range(n)]\n",
    "        dp_left[1] = nums[0]\n",
    "        for i in range(2, n):\n",
    "            dp_left[i] = max(dp_left[i - 1], nums[i - 1])\n",
    "            pass\n",
    "\n",
    "        dp_right = [sys.maxsize for _ in range(n)]\n",
    "        dp_right[n - 2] = nums[n - 1]\n",
    "        for i in range(n - 3, 0, -1):\n",
    "            dp_right[i] = min(dp_right[i + 1], nums[i+1])\n",
    "            pass\n",
    "\n",
    "        for i in range(1, len(nums) - 1):\n",
    "            res = self.get_v(nums, dp_left, dp_right, i)\n",
    "            result += res\n",
    "            pass\n",
    "        return result\n",
    "\n",
    "    pass\n",
    "\n",
    "\n",
    "    def get_v(self, nums, dp_left, dp_right, i):\n",
    "        if dp_left[i] < nums[i] < dp_right[i]:\n",
    "            # nums[j]-->max,nums[k]-->min\n",
    "            # max < i < min\n",
    "            return 2\n",
    "            pass\n",
    "        elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        dp_left = [float('-inf')] * n\n",
    "        dp_left[1] = nums[0]\n",
    "        for i in range(2, n):\n",
    "            dp_left[i] = max(dp_left[i - 1], nums[i - 1])\n",
    "            pass\n",
    "\n",
    "        dp_right = [sys.maxsize] * n\n",
    "        dp_right[n - 2] = nums[n - 1]\n",
    "        for i in range(n - 3, 0, -1):\n",
    "            dp_right[i] = min(dp_right[i + 1], nums[i+1])\n",
    "            pass\n",
    "\n",
    "        for i in range(1, len(nums) - 1):\n",
    "            res = self.get_v(nums, dp_left, dp_right, i)\n",
    "            result += res\n",
    "            pass\n",
    "        return result\n",
    "\n",
    "    pass\n",
    "\n",
    "\n",
    "    def get_v(self, nums, dp_left, dp_right, i):\n",
    "        if dp_left[i] < nums[i] < dp_right[i]:\n",
    "            # nums[j]-->max,nums[k]-->min\n",
    "            # max < i < min\n",
    "            return 2\n",
    "            pass\n",
    "        elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        left = []\n",
    "        right = []\n",
    "        cur = 0\n",
    "        for n in nums:\n",
    "            cur = max(cur,n)\n",
    "            left.append(cur)\n",
    "        cur = 999999999\n",
    "        for n in nums[::-1]:\n",
    "            cur = min(cur,n)\n",
    "            right.append(cur)\n",
    "        right = right[::-1]\n",
    "        res = 0\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if nums[i] > left[i-1] and nums[i] < right[i+1]:\n",
    "                res += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        min_state = [0] * n\n",
    "        min_state[-1] = nums[-1]\n",
    "        max_state = [0] * n\n",
    "        max_state[0] = nums[0]\n",
    "        state = [0] * n\n",
    "        for i in range(1,n):\n",
    "            max_state[i] = max(max_state[i-1], nums[i])\n",
    "        for i in range(n-2,-1,-1):\n",
    "            min_state[i] = min(min_state[i+1], nums[i])\n",
    "        for i in range(1,n-1):\n",
    "            if nums[i] > max_state[i-1] and nums[i] < min_state[i+1]:\n",
    "                state[i] = 2\n",
    "            elif nums[i] > nums[i-1] and nums[i] < nums[i+1]:\n",
    "                state[i] = 1\n",
    "            else:\n",
    "                state[i] = 0\n",
    "        return sum(state)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        a = nums[:n-2] + [0,0]\n",
    "        res = nums[0]\n",
    "        for i in range(1,n-2):\n",
    "            a[i] = max(res,a[i])\n",
    "            res = a[i]\n",
    "        \n",
    "        b = [0,0] + nums[2:]\n",
    "        res = nums[-1]\n",
    "        for i in range(2,n-1):\n",
    "            b[-i] = min(res,b[-i])\n",
    "            res = b[-i]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1,n-1):\n",
    "            if nums[i] > a[i-1] and nums[i] < b[i+1]:\n",
    "                ans += 2\n",
    "            elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        sl=SortedList(nums[2:])\n",
    "        m=nums[0]\n",
    "        ans=0\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if nums[i]>m and nums[i]<sl[0]:\n",
    "                ans+=2\n",
    "            elif nums[i]>nums[i-1] and nums[i]<nums[i+1]:\n",
    "                ans+=1\n",
    "            m=max(m,nums[i])\n",
    "            sl.remove(nums[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        from sortedcontainers import SortedList\n",
    "        left = SortedList(nums[:1])\n",
    "        right = SortedList(nums[1:])\n",
    "        for i in range(1, n-1):\n",
    "            x = nums[i]\n",
    "            right.remove(x)\n",
    "            if left[-1] < x < right[0]:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < x < nums[i+1]:\n",
    "                ans += 1\n",
    "            left.add(x)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1,n-1):\n",
    "            if nums[i-1]<nums[i]<nums[i+1]:\n",
    "                s += 1\n",
    "\n",
    "        fma = list(range(n))\n",
    "        fmi = list(range(n))\n",
    "        black = set()\n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                fma[i] = nums[i]\n",
    "                fmi[n-i-1] = nums[n-i-1]\n",
    "            else:\n",
    "                fma[i] = max(fma[i-1],nums[i])\n",
    "                if fma[i-1] == nums[i]:\n",
    "                    black.add(fma[i])\n",
    "                fmi[n-i-1] = min(fmi[n-i],nums[n-i-1])\n",
    "                if fmi[n-i]==nums[n-i-1]:\n",
    "                    black.add(fmi[n-i])\n",
    "        \n",
    "        t = 0\n",
    "        for k in range(1,n-1):\n",
    "            i = fma[k]\n",
    "            j = fmi[k]\n",
    "            if i==j and j not in black:\n",
    "                t+=1\n",
    "        return s+t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        # 对于 i，找左边j nums[j]>=nums[i]\n",
    "        # 找右边 nums[k] <= nums[i]\n",
    "        # 都没找到，就是2\n",
    "        # 找到了，但是j < i - 1 and k > i + 1就是1\n",
    "        # 否则就是0\n",
    "\n",
    "        n = len(nums)\n",
    "        # 找右边小于\n",
    "        aft = [-1 for _ in range(n)]\n",
    "        stk = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while stk and nums[stk[-1]] >= x:\n",
    "                tmp = stk.pop()\n",
    "                aft[tmp] = i\n",
    "            stk.append(i)\n",
    "        #找左边大于\n",
    "        pre = [-1 for _ in range(n)]\n",
    "        stk = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stk and nums[stk[-1]] <= nums[i]:\n",
    "                pre[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n-1):\n",
    "            if aft[i] < 0 and pre[i] < 0:\n",
    "                ans += 2\n",
    "            elif nums[i-1] < nums[i] < nums[i+1]:\n",
    "                ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfBeauties(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        cached = [[0, 0] for _ in range(n)]\n",
    "        cached[1][0] = nums[0]\n",
    "        cached[n - 2][1] = nums[n - 1]\n",
    "        p1, p2 = 1, len(nums) - 2\n",
    "        for i in range(2, len(nums)):\n",
    "            cached[i][0] = max(cached[i - 1][0], nums[i - 1])\n",
    "            cached[n - i - 1][1] = min(cached[n - i][1], nums[n - i])\n",
    "            pass\n",
    "\n",
    "        for i in range(1, len(nums) - 1):\n",
    "            res = self.get_v(nums, cached, i)\n",
    "            result += res\n",
    "            pass\n",
    "        return result\n",
    "\n",
    "    pass\n",
    "\n",
    "    def get_v(self, nums,cached, i):\n",
    "        if cached[i][0] < nums[i] < cached[i][1]:\n",
    "            # nums[j]-->max,nums[k]-->min\n",
    "            # max < i < min\n",
    "            return 2\n",
    "            pass\n",
    "        elif nums[i - 1] < nums[i] < nums[i + 1]:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "        pass"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
